package com.hzchendou.blog.code.chapter02.example04;

/**
 * 替换空格.
 *
 * @author hzchendou
 * @date 2022/10/19
 * @since 1.0
 */
public class Example {
    //// 面试题4: 替换空格
    //// 题目：请实现一个函数,把字符串中的每个空格替换成 "%20",
    //// 例如输入 "We are Happy", 则输出 "We%20are%20Happy"

    /**
     * 输入字符串，替换字符串中的每一个空格
     *
     * @param str
     * @return
     */
    public static String m1(String str) {
        return str.replaceAll(" ", "%20");
    }

    /**
     * 从前往后进行遍历，遇到空格，将字符串后移2位（' ' -> '%20', 增加了两个字节）
     * 将空格替换成 %20, 时间复杂度为 o(n ^ 2), 两个循环，增加了时间复杂度
     * @param str
     * @return
     */
    public static String m2(char[] str) {
        char[] s = str;
        int len = s.length;
        for (int i = 0; i < len; i++) {
            if (s[i] == ' ') {
                s = move(s, i, 2);
                len = s.length;
                s[i] = '%';
                s[++i] = '2';
                s[++i] = '0';
            }
        }
        return new String(s);
    }

    /**
     * 从m2可以知道，增加的时间来自字符数组扩容操作，每遇到一个空格都要移动后续字符，如果已经知道了新字符串的长度
     * 那么直接赋值即可，因此首先遍历字符串查找空格数，确定新数组长度
     * @param str
     * @return
     */
    public static String m3(char[] str) {
        int len = str.length;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == ' ') {
                len += 2;
            }
        }
        char[] newStr = new char[len];
        int i = 0;
        int y = 0;
        while (i < str.length) {
            if (str[i] == ' ') {
                newStr[y] = '%';
                newStr[++y] = '2';
                newStr[++y] = '0';
            } else {
                newStr[y] = str[i];
            }
            i++;
            y++;
        }
        return new String(newStr);
    }

    /**
     * 将字符数组str中的i位置开始往后移动offset位
     *
     * @param str
     * @param i
     * @param offset
     * @return
     */
    public static char[] move(char[] str, int i, int offset) {
        int newLen = str.length + offset;
        char[] newStr = new char[newLen];
        for (int x = 0; x < newStr.length; x++) {
            if (x < i) {
                newStr[x] = str[x];
            } else if (x >= i + offset) {
                newStr[x] = str[x - offset];
            } else {
                newStr[x] = ' ';
            }
        }
        return newStr;
    }

    public static void main(String[] args) {
        String str = "We are Happy";
        System.out.println(m1(str));
        System.out.println(m2(str.toCharArray()));
        System.out.println(m3(str.toCharArray()));
    }
}
